package src.tree;

public class no111 {//二叉树最小深度
    // 最小深度是从根节点到最近叶子节点的最短路径上的节点数量

    //后序
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        if (root.left != null && root.right == null) return left + 1;
        if (root.left == null && root.right != null) return right + 1;

        //左右都不为空时
        return Math.min(left, right) + 1;
    }

    //前序
    public int minDepth2(TreeNode root) {
        if (root == null) return 0;
        preOrder(root, 1);
        return height;
    }

    int height = Integer.MAX_VALUE;  //注意要初始化为一个很大的数，不能是 0

    public void preOrder(TreeNode node, int n) {
        if (node == null) return;
        //每次遍历到叶子时，保留一个最小深度
        if (node.left == null && node.right == null) height = Math.min(height, n);
        preOrder(node.left, n + 1);
        preOrder(node.right, n + 1);

    }

}
